package 图.有向图;

import 抽象数据类型.Bag;
import 抽象数据类型.Digraph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-06
 */
public class 拓扑排序BFS {
    public static void main(String[] args) {
        int[] arr1 = {2, 1, 2, 3, 0};
        int[] arr2 = {1, 3, 3, 4, 4};
        Digraph G = new Digraph(arr1.length);
        G.addDigraph(arr1, arr2);
        Degrees degrees = new Degrees(G);
        TopologicalBFS(degrees);

    }

    public static void TopologicalBFS(Degrees degrees) {
        Digraph g = degrees.g;
        Queue<Integer> queue = new LinkedList();
        for (Integer source : degrees.sources()) {
            queue.offer(source);
        }
        while (!queue.isEmpty()) {
            Integer w = queue.poll();
            System.out.println(w);
            for (Integer v : g.adj(w)) {
                degrees.indegree[v]--;
                if (degrees.indegree[v] == 0 ) {
                    queue.offer(v);
                }
            }
          }

    }

    public static class Degrees {
        public int[] indegree;
        public int[] outdegree;
        public Digraph g;

        public Degrees(Digraph g) {
            indegree = new int[g.V()];
            this.g = g;
            indegree = new int[g.V()];
            outdegree = new int[g.V()];
            for (int v = 0; v < g.V(); v++) {
                for (Integer w : g.adj(v)) {
                    indegree[w]++;
                    outdegree[v]++;
                }
            }
        }

        public int indegree(int v) {
            return indegree[v];
        }

        public int outdegree(int v) {
            return outdegree[v];
        }

        public Iterable<Integer> sources() {
            Bag<Integer> bag = new Bag<>();
            for (int v = 0; v < g.V(); v++) {
                if (indegree[v] == 0) {
                    bag.add(v);
                }
            }
            return bag;
        }

        public Iterable<Integer> sinks() {
            Bag<Integer> bag = new Bag<>();
            for (int v = 0; v < g.V(); v++) {
                if (outdegree[v] == 0) {
                    bag.add(v);
                }
            }
            return bag;
        }

        public boolean isMap() {
            Bag<Integer> bag = new Bag<>();
            for (int i = 0; i < g.V(); i++) {
                if (outdegree[i] != 1) {
                    return false;
                }
            }
            return true;
        }
    }
}
